package com.gubatian.demo.algorithm.simple;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Description: 有效的括号
 * @author: GuBaTian
 * @date: 2021/09/15
 */
public class ValidParentheses {

    private static Set<String> parentheses = new HashSet<>();
    static {
        parentheses.add("[]");
        parentheses.add("{}");
        parentheses.add("()");
        parentheses.add("<>");
    }
    public boolean isValid(String s) {
        // 首先有对应关系，如果s.length是奇数肯定无法闭合
        // 如果s.length是偶数，从中间截断
        // 第一个字符串的尾部对应第二个字符串的尾部
        // 如果头部和尾部不能闭合则返回true

        final int len = (s == null) ? 0 : s.length();
        // 判断字符串是否为空。为空返回false
        if (len == 0) {
            return false;
        }
        // 判断字符串长度是否为奇数
        if (len % 2 != 0) {
            return false;
        }
        final int mid = len / 2;
        // 字符长度为偶数，从中间截断
        // 左半边字符串
        final String left = s.substring(0, mid);
        // 右半边字符串
        final String right = s.substring(mid);
        return compareStr(left, right, mid);
    }
    // 比较left从尾部开始和right头部开始是否闭合
    // 如果没有闭合返回false
    // 如果闭合了，继续比较
    public boolean compareStr(String left, String right, final int len) {
        // 如果长度为0了说明已经比较完了
        if (len == 0) {
            return true;
        }
        // 左边字符串最后一位
        final String leftTail = left.substring(len - 1, len);
        // 右边字符串头部一位
        final String rightHead = right.substring(0, 1);
        // 左边和右边如果没有闭合直接返回false
        if (!parentheses.contains(leftTail + rightHead)) {
            return false;
        }
        // 剩下的字符长度
        final int remainLen = len - 1;
        // 如果长度为0了说明已经比较完了
        if (remainLen == 0) {
            return true;
        }
        // 左边剩下的字符串
        final String leftRemain = left.substring(0, len - 1);
        // 右边剩下的字符串
        final String rightRemain = right.substring(1, len);

        return compareStr(leftRemain, rightRemain, remainLen);
    }

    public static void main(String[] args) {
        ValidParentheses validParentheses = new ValidParentheses();
        boolean result = validParentheses.isValid("[{(}}]");
        System.out.println(result);
    }
}
